package 力扣_排序算法.快排;

import java.util.Random;

/**
 * @author zx
 * @create 2022-08-10 23:49
 */
public class 颜色分类_75 {
    public void sortColors(int[] nums) {
        Random rnd = new Random();
        partition(nums, 0, nums.length - 1, rnd);
    }
    private void partition(int[] arr, int l, int r, Random rnd){
        if(r - l <= 0){
            return;
        }
        int p = l + rnd.nextInt(r - l + 1);
        swap(arr, l, p);
        int v = arr[l];
        int lt = l;
        int i = lt + 1;
        int gt = r + 1;
        while(i < gt){
            if(arr[i] < v){
                swap(arr, i, lt + 1);
                i++;
                lt++;
            }else if(arr[i] > v){
                swap(arr, i, gt - 1);
                gt--;
            }else if(arr[i] == v){
                i++;
            }
        }
        swap(arr, l, lt);
        partition(arr,l,lt - 1, rnd);
        partition(arr, gt, r, rnd);
    }
    private void swap(int[] arr, int left, int right){
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }
}
